package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月26日
*时间：下午9:46:04
*/
public class Q31 {
    /** 
     *@param nums: The integer array you should partition
     *@param k: As description
     *return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[right] >= k) {
                right--;
            }
            change(nums, left, right);
            while (left < right && nums[left] < k) {
                left++;
            }
            change(nums, left, right);
        }
        return left == nums.length - 1 ? nums.length : nums[left] < k ? left + 1 : left;
    }

    private void change(int[] nums, int left, int right) {
        int v = nums[left];
        nums[left] = nums[right];
        nums[right] = v;
    }

    @Test
    public void testA() {
        int[] nums = { 66, 80, 165, 139, 187, 116, 77, 97, 40, 181, 115, 31, 123, 123, 44, 119, 108, 142, 146, 128, 104, 172, 170, 171, 197, 61, 119, 198, 110,
                32, 46, 146, 96, 28, 151, 30, 55, 65, 199, 147, 61, 155, 44, 113, 120, 177, 70, 38, 76, 174, 42, 158, 148, 50, 151, 180, 97, 49, 169, 81, 46,
                192, 67, 133, 40, 24, 75, 171, 47, 187, 77, 46, 81, 108, 94, 38, 63, 114, 195, 173, 124, 68, 92, 105, 157, 81, 57, 158, 181, 91, 132, 73, 147,
                186, 151, 71, 58, 115, 38, 198, 60, 162, 44, 134, 52, 82, 192, 84, 49, 72, 123, 22, 76, 169, 162, 40, 72, 144, 61, 67, 37, 198, 73, 112, 188,
                180, 180, 171, 156, 167, 58, 70, 37, 185, 57, 144, 121, 94, 158, 43, 34, 147, 200, 37, 90, 32, 124, 136, 52, 118, 136, 159, 181, 53, 169, 95,
                70, 153, 95, 27, 196, 185, 40, 100, 93, 135, 40, 87, 73, 192, 92, 26, 108, 192, 139, 39, 120, 37, 46, 44, 189, 170, 190, 44, 103, 54, 109, 175,
                159, 61, 35, 134, 92, 72, 109, 149, 83, 46, 107, 167, 133, 164, 46, 37, 32, 149, 20, 42, 81, 66, 69, 68, 83, 88, 165, 139, 95, 89, 21, 119, 90,
                127, 197, 114, 84, 183, 134, 160, 60, 124, 140, 83, 154, 154, 132, 163, 105, 80, 163, 90, 89, 178, 102, 189, 177, 109, 165, 168, 33, 146, 105,
                55, 22, 169, 92, 83, 135, 155, 45, 164, 67, 155, 159, 151, 189, 177, 46, 99, 120, 28, 97, 65, 159, 126, 191, 24, 42, 32, 187, 150, 115, 137,
                32, 58, 56, 72, 52, 58, 175, 29, 153, 129, 20, 43, 67, 182, 134, 137, 189, 35, 112, 115, 107, 117, 119, 127, 184, 149, 37, 152, 83, 143, 157,
                138, 61, 90, 172, 118, 143, 108, 59, 145, 193, 131, 95, 100, 126, 133, 130, 153, 69, 45, 110, 57, 30, 153, 63, 63, 143, 71, 57, 163, 149, 27,
                140, 54, 20, 95, 88, 168, 28, 108, 153, 53, 170, 21, 52, 173, 132, 159, 178, 59, 197, 21, 138, 179, 42, 66, 97, 129, 30, 158, 152, 69, 26, 87,
                184, 105, 32, 20, 79, 167, 94, 22, 107, 173, 145, 128, 57, 55, 180, 23, 191, 46, 173, 134, 70, 120, 178, 110, 105, 152, 187, 195, 30, 186, 70,
                197, 75, 101, 125, 91, 108, 86, 24, 190, 168, 100, 71, 53, 33, 124, 114, 123, 176, 52, 181, 99, 165, 187, 144, 145, 145, 102, 50, 135, 132,
                177, 116, 101, 131, 103, 194, 74, 145, 141, 73, 46, 58, 129, 142, 109, 113, 127, 183, 191, 140, 168, 34, 115, 85, 43, 187, 153, 127, 192, 168,
                101, 117, 115, 61, 48, 84, 200, 41, 178, 21, 23, 99, 55, 32, 178, 175, 147, 27, 68, 44, 95, 186, 139, 192, 128, 95, 159, 184, 183, 153, 185,
                39, 184, 198, 128, 195, 55, 44, 101, 44, 35, 101, 101, 124, 50, 110, 109, 97, 133, 99, 65, 42, 154, 43, 184, 76, 108, 113, 58, 68, 108, 128,
                174, 56, 172, 83, 173, 150, 113, 123, 112, 23, 171, 68, 116, 44, 191, 133, 72, 77, 65, 173, 36, 140, 36, 56, 163, 122, 111, 36, 101, 137, 195,
                85, 49, 157, 159, 175, 86, 108, 158, 71, 100, 149, 177, 174, 127, 40, 128, 21, 36, 72, 88, 182, 129, 88, 126, 108, 124, 49, 155, 93, 146, 186,
                78, 167, 171, 49, 192, 89, 102, 198, 160, 126, 130, 182, 197, 177, 138, 162, 46, 85, 46, 30, 99, 173, 175, 90, 58, 50, 139, 197, 144, 71, 155,
                101, 52, 161, 162, 22, 133, 119, 141, 68, 88, 190, 184, 111, 118, 119, 172, 198, 20, 132, 153, 131, 180 };
        int k = 131;
        System.out.println(partitionArray(nums, k));
    }
}
